const Dictionay = require('../04-字典结构/00-封装字典')
const Queue = require('../01-队列结构/00-封装队列')

function Graph() {
  this.vertexes = [] // 顶点(似乎可以不需要，直接使用this.edges.keys当作顶点)
  this.edges = new Dictionay() // 边

  // 1.添加顶点
  Graph.prototype.addVertex = function(vertex) {
    this.vertexes.push(vertex)
    this.edges.set(vertex, [])
  }

  // 2.添加边（无向图）
  Graph.prototype.addEdge = function(vertex1, vertex2) {
    this.edges.get(vertex1).push(vertex2)
    this.edges.get(vertex2).push(vertex1)
  }

  // 3.打印 ---> toString方法
  Graph.prototype.toString = function() {
    let str = ''
    this.vertexes.forEach(vertex => {
      str += '\n' + vertex + ' -> '
      this.edges.items[vertex].forEach(edge => {
        str += edge + ' '
      })
    })
    return str.trim()
  }

  // 初始化状态颜色
  Graph.prototype.initializeColor = function() {
    let colors = []
    for (let i = 0; i < this.vertexes.length; i++) {
      colors[this.vertexes[i]] = 'white'
    }
    return colors
  }

  // 4.实现广度优先搜素
  Graph.prototype.bfs = function(initVertex, handler) {
    // 1.初始化状态颜色
    /**
     * 状态颜色有三种，
     * > 白色 -> 还没有被访问
     * > 灰色 -> 被访问但没有被探索过
     * > 黑色 -> 被访问并且被完全探索过
     */
    // 得到含有状态颜色的顶点，以键值对的形式存储
    let colors = this.initializeColor()

    // 2.创建顶点队列
    let vertexQueue = new Queue()

    // 3.把顶点加入到队列中,从initVertex开始做广度搜素
    vertexQueue.enqueue(initVertex)

    // 4.开始访问顶点队列
    while (!vertexQueue.isEmpty()) {
      // 4.1取出顶点
      let vertex = vertexQueue.dequeue()

      // 4.2 修改vertex状态为被访问但未探索
      colors[vertex] = 'gray'

      // 4.3 开始探索，得到vertex顶点的相邻顶点
      let vertexList = this.edges.get(vertex)

      // 4.4 把探索得到的相邻顶点加入到顶点队列（ 根据状态去重）
      vertexList.forEach(adjacentVertex => {
        if (colors[adjacentVertex] === 'white') {
          vertexQueue.enqueue(adjacentVertex)
          colors[adjacentVertex] = 'gray'
        }
      })

      // 4.5将顶点状态修改为完全探索
      colors[vertex] = 'black'

      // 4.6处理handler
      handler(vertex)
    }
  }

  // 5.实现深度优先搜素
  Graph.prototype.dfs = function(initVertex, handler) {
    // 1.初始化状态颜色
    let colors = this.initializeColor()

    // 2.从某个顶点开始递归访问
    this.dfsRecursive(initVertex, colors, handler)

  }

  // 深度搜索递归函数
  Graph.prototype.dfsRecursive = function(initVertex, colors, handler) {
    // 1.修改状态颜色为被访问但未完全搜索
    colors[initVertex] = 'gray'

    // 2.处理顶点
    handler(initVertex)

    // 3.开始探索，得到vertex顶点的相邻顶点
    let vertexList = this.edges.get(initVertex)

    //4. 访问邻近顶点（ 根据状态去重）
    vertexList.forEach(adjacentVertex => {
      if (colors[adjacentVertex] === 'white') {
        this.dfsRecursive(adjacentVertex, colors, handler)
      }
    })

    // 5.修改颜色状态为完全搜索
    colors[initVertex] = 'balck'
  }
}

module.exports = Graph


// 测试代码
var graph = new Graph()

// 添加顶点
var myVertexes = ["A", "B", "C", "D", "E", "F", "G", "H", "I"]
for (var i = 0; i < myVertexes.length; i++) {
  graph.addVertex(myVertexes[i])
}

// 添加边
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('E', 'I');
// console.log(graph.toString());
// graph.bfs(graph.vertexes[0], function(vertex) {
//   console.log(vertex);
// })
graph.dfs(graph.vertexes[0], function(vertex) {
  console.log(vertex);
})
console.log(graph.toString());